#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/5 17:25
# @USER    : Shengji He
# @File    : ValidParentheses.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:


class Solution:
    def isValid(self, s: str) -> bool:
        """
        Given a string containing just the characters '(', ')', '{', '}', '[' and ']',
        determine if the input string is valid.

        An input string is valid if:
            1. Open brackets must be closed by the same type of brackets.
            2. Open brackets must be closed in the correct order.
        Note that an empty string is also considered valid.

        Example 1:
            Input: "()"

            Output: true
        Example 2:
            Input: "()[]{}"

            Output: true
        Example 3:
            Input: "(]"

            Output: false
        Example 4:
            Input: "([)]"

            Output: false
        Example 5:
            Input: "{[]}"

            Output: true

        :param s: str
        :return: bool
        """
        ans = ''
        for ele in list(s):
            if ele in ['(', '[', '{']:
                ans += ele
            elif ele in [')', ']', '}']:
                if ans and ans[-1] == ['(', '[', '{'][[')', ']', '}'].index(ele)]:
                    ans = ans[:-1]
                else:
                    return False
            else:
                continue
        return [False, True][not ans]


if __name__ == '__main__':
    S = Solution()
    s = '(([](){}sa)'
    print(S.isValid(s))
    print('done')
